#include<bits/stdc++.h>
using namespace std;
int n,m,t1[1005]={0},tit[1005]={0},ans[1005][1005]={0},tiee=0,num=0;
void dfs(int index,int nub){
	for(int i=0;i<n;i++){
		if(num==n&&ans[index][nub]==1){
			tiee=1;return ;
		}			
		if(ans[index][i]==1&&tit[i]==0){
			num++;
			tit[i]=1;
			dfs(i,nub);
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		ans[x][y]=ans[y][x]=1;
		t1[x]++;
		t1[y]++;
	}
	for(int i=0;i<n;i++){
		if(t1[i]%2!=0){
			cout<<"0";return 0;
		}
	}
	num++;
	dfs(1,1);
	cout<<tiee;
	return 0;
 }
 
 
